package a04_字符串;

import java.util.Arrays;

/**
 * <p>
 * a07_重复的子字符串
 * abcabcabcabc
 *             12 % (12-9) = 0
 *
 *
 * @author flyduck
 * @since 2024-07-11
 */
public class a07_重复的子字符串复习3 {

    public static void main(String[] args) {
        String s = "abac";
//        String s = "aabaab";
        System.out.println(Arrays.toString(getNextArray(s.toCharArray())));

        System.out.println(repeatedSubstringPattern(s));
    }

    public static boolean repeatedSubstringPattern(String s) {
        char[] chars = s.toCharArray();
        int[] nextArray = getNextArray(chars);
        if(nextArray[nextArray.length - 1] == 0){
            return false;
        }
        return chars.length % (chars.length - nextArray[nextArray.length - 1]) == 0;
    }

    public static int[] getNextArray(char[] chars){
        if(chars.length == 0){
            int[] nextArray = new int[1];
            nextArray[0] = -1;
            nextArray[1] = 0;
            return nextArray;
        }

        int[] nextArray = new int[chars.length + 1];
        nextArray[0] = -1;
        nextArray[1] = 0;
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];
        while (currentIdx < nextArray.length) {
            if(chars[compareIdx] == chars[currentIdx - 1]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if (compareIdx == 0) {
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;
    }




}
